﻿#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

//2. 两数相加
//https://leetcode.cn/problems/add-two-numbers/

struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* newhead = new ListNode(0);
        ListNode* cur1 = l1, * cur2 = l2;
        ListNode* cur = newhead;
        int c = 0;
        while (cur1 || cur2 || c) {
            if (cur1) {
                c += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2) {
                c += cur2->val;
                cur2 = cur2->next;
            }
            cur->next = new ListNode(c % 10);
            cur = cur->next;
            c /= 10;
        }
        cur = newhead->next;
        delete newhead;
        return cur;
    }
};

//24. 两两交换链表中的节点
//https://leetcode.cn/problems/swap-nodes-in-pairs/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* newHead = new ListNode(0);
        newHead->next = head;
        ListNode* prev = newHead, * cur = prev->next, * next = cur->next,
            * nnext = next->next;
        while (cur && next) {
            prev->next = next;
            next->next = cur;
            cur->next = nnext;
            prev = cur;
            cur = prev->next;
            if (cur)
                next = cur->next;
            if (next)
                nnext = next->next;
        }
        cur = newHead->next;
        delete newHead;
        return cur;
    }
};

//143. 重排链表
//https://leetcode.cn/problems/reorder-list/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == nullptr || head->next == nullptr ||
            head->next->next == nullptr) {
            return;
        }
        ListNode* slow = head, * fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* rhead = new ListNode(0);
        ListNode* cur = slow->next;
        slow->next = nullptr;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = rhead->next;
            rhead->next = cur;
            cur = next;
        }
        ListNode* cur1 = head, * cur2 = rhead->next;
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        while (cur1) {
            prev->next = cur1;
            cur1 = cur1->next;
            prev = prev->next;
            if (cur2) {
                prev->next = cur2;
                cur2 = cur2->next;
                prev = prev->next;
            }
        }
        delete rhead;
        delete ret;
    }
};

//23. 合并 K 个升序链表
//https://leetcode.cn/problems/merge-k-sorted-lists/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//优先级队列
class Solution {
public:
    struct cmp {
        bool operator()(const ListNode* a, const ListNode* b) {
            return a->val > b->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        for (auto l : lists) {
            if (l)
                heap.push(l);
        }
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        while (!heap.empty()) {
            ListNode* t = heap.top();
            heap.pop();
            prev->next = t;
            prev = t;
            if (t->next)
                heap.push(t->next);
        }
        prev = ret->next;
        delete ret;
        return prev;
    }
};
//思路二：递归/分治 
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }

    ListNode* merge(vector<ListNode*>& lists, int left, int right) {
        int mid = left + right >> 1;
        if (left > right)
            return nullptr;
        if (left == right)
            return lists[left]; // 只有一个链表

        ListNode* l1 = merge(lists, left, mid);
        ListNode* l2 = merge(lists, mid + 1, right);

        return mergeTwoList(l1, l2);
    }

    ListNode* mergeTwoList(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;

        ListNode head;
        ListNode* cur1 = l1, * cur2 = l2, * prev = &head;
        head.next = nullptr;

        while (cur1 && cur2) {
            if (cur1->val <= cur2->val) {
                prev = prev->next = cur1;
                cur1 = cur1->next;
            }
            else {
                prev = prev->next = cur2;
                cur2 = cur2->next;
            }
        }

        if (cur1)
            prev->next = cur1;
        if (cur2)
            prev->next = cur2;

        return head.next;
    }
};

//25. K 个一组翻转链表
//https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int n = 0;
        ListNode* cur = head;
        while (cur) {
            cur = cur->next;
            n++;
        }
        n /= k;
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        cur = head;
        for (int i = 0; i < n; i++) {
            ListNode* tmp = cur;
            for (int j = 0; j < k; j++) {
                ListNode* next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev->next = cur;
        cur = newhead->next;
        delete newhead;
        return cur;
    }
};